\documentclass[11pt]{ctexart}
\usepackage{tabularx}
\usepackage{array}
\usepackage{bm}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{algorithm}
%\usepackage{algorithm2e}
\usepackage{algorithmicx}
\usepackage{algpseudocode}
\usepackage{fancyhdr}
\pagestyle{fancy}

\hypersetup{hypertex=true,
	colorlinks=true,
	linkcolor=red,
	anchorcolor=blue,
	citecolor=blue}

\fancyhf{}
\chead{\textbf{计算方法}}
\fancyhead[r]{\bfseries\thepage}
\fancyhead[l]{\bfseries\rightmark}
\renewcommand{\headrulewidth}{0.4pt} % 注意不用 \setlength
\renewcommand{\footrulewidth}{0pt}

\floatname{algorithm}{算法}
\renewcommand{\algorithmicrequire}{\textbf{输入:}}
\renewcommand{\algorithmicensure}{\textbf{输出:}}
\begin{titlepage}
	\title{\Huge\textbf{计算方法作业一、二}\\}
	\author{\Large\textbf{作者}：吴润泽 \and{\Large\textbf{学号}：181860109}\\
		\\
		\and {\Large\textbf{Email}：\href{mailto:181860109@smail.nju.edu.cn}{181860109@smail.nju.edu.cn}}\\}
	\date{\Large\today}
\end{titlepage}

\begin{document}
	\maketitle
	\tableofcontents
	\newpage
	\section*{assignment I}
	\markright{assignment I}
	\addcontentsline{toc}{section}{assignment I}
	\section*{problem 11}
	\markright{problem 11}
	\addcontentsline{toc}{subsection}{problem 11}
	\paragraph{解：}
	设$\bar{y}_n$为$y_n$的近似值，$\varepsilon^*(y_n)=\bar{y}_n-y_n$，递推关系式有:
	$$\begin{aligned}
	y_n&=10y_{n-1}-1=10(10y_{n-2}-1)-1\\
	&=10^2y_{n-2}-(1+10^1)\\
	&=10^2(10y_{n-3}-1)-(1+10^1)\\
	&=10^3y_{n-3}-(1+10^1+10^2)\\
	&=\cdots\\
	&=10^ny_0-\sum_{i=0}^{n-1}10^i\\
	&=10^ny_0-\frac{1}{9}(10^n-1)\\
	\end{aligned}
	$$
	又有$y_0=\sqrt{2},\bar{y}_0=1.41\Rightarrow\varepsilon^*(y_0)=\frac{1}{2}\times10^{-2}$，即：
	$$\begin{aligned}
	&y_{10}=10^{10}\cdot\sqrt{2}-\frac{1}{9}(10^{10}-1),\bar{y_{10}}=10^{10}\cdot1.41-\frac{1}{9}(10^{10}-1),\\
	&\varepsilon^*(y_{10})=10^{10}\varepsilon^*(y_0)=10^{10}\times \frac{1}{2}\times10^{-2}=\frac{1}{2}\times10^8.\\
	\end{aligned}
	$$
	因为$y_{10}$的误差限是$y_0$误差限的$10^{10}$倍，因此计算过程不稳定。
	\section*{problem 13}
	\markright{problem 13}
	\addcontentsline{toc}{subsection}{problem 13}
	\paragraph{解：}
	首先对于开方运算：
	\begin{align}
	u=\sqrt{30^2-1}=\sqrt{899}\approx29.9833\ , \varepsilon^*(u)=\frac{1}{2}\times10^{-4}
	\end{align}
	对于对数函数1：$f_1(x)=\ln({x-\sqrt{x^2-1}}),f_1(u)=\ln(30-u):$
	\begin{align}
	\varepsilon^{*}(f_1(u))&=|f_1^{'}(u^{*})|\varepsilon^*(u)
	\approx|\frac{1}{30-u^{*}}|\times\frac{1}{2}\times10^{-4}\notag\\
	&=|\frac{1}{30-29.9833}|\times\frac{1}{2}\times10^{-4}\notag\\
	&\approx 3\times 10^{-3}
	\end{align}
	对于对数函数2：$f_2(x)=\ln({x+\sqrt{x^2-1}}),f_2(u)=-\ln(30+u):$
	\begin{align}
	\varepsilon^{*}(f_2(u))&=|f_2^{'}(u^{*})|\varepsilon^*(u)
	\approx|\frac{1}{30+u^{*}}|\times\frac{1}{2}\times10^{-4}\notag\\
	&=|\frac{1}{30+29.9833}|\times\frac{1}{2}\times10^{-4}\notag\\
	&\approx 8\times 10^{-7}
	\end{align}
	因此用等价公式$\ln({x+\sqrt{x^2-1}})$计算误差较小
	\newpage
	\section*{assignment II}
	\markright{assignment II}
	\addcontentsline{toc}{section}{assignment II}
	\subsection*{problem 2}
	\markright{problem 2}
	\addcontentsline{toc}{subsection}{problem 2}
	$
	\begin{aligned}
	&l_0(x)=\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)}=-\frac{1}{2}(x+1)(x-2)\\
	&l_1(x)=\frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)}=\frac{1}{6}(x-1)(x-2)\\
	&l_2(x)=\frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)}=\frac{1}{3}(x-1)(x+1)\\
	\text{因此}\\
	p_2(x)&=y_0l_0(x)+y_1l_1(x)+y_2l_2(x)\\
	&=-\frac{1}{2}(x-1)(x-2)+\frac{4}{3}(x-1)(x+1)\\
	\end{aligned}
	$
	\subsection*{problem 3}
	\markright{problem 3}
	\addcontentsline{toc}{subsection}{problem 3}

	\begin{table}[h]
		\centering
		\caption{函数及均差表}
		\begin{tabular}{|c|c|c|c|}
			\hline
			0.5 & \textbf{-0.693147}     & & \\
			0.6 & -0.510826          & \textbf{1.82321}          &      \\
			0.7 & -0.357765          & 1.53061          & \textbf{-1.46300}  \\
			\hline
		\end{tabular}
	\end{table}
	
	\paragraph{线性插值法}
	$
	\begin{aligned}
	P_1(0.54)&=-0.693147+f[0.5,0.6](0.54-0.5)\\
	&=-0.693147+1.82321\times(0.54-0.5)\\
	&\approx-0.620219\\
	\end{aligned}
	$\\
	则$\ln 0.54\approx P_1(0.54)\approx-0.620219$\\
	\paragraph{二次插值法}
	$
	\begin{aligned}
	P_2(0.54)&=P_1(0.54)+f[0.5,0.6,0.7](0.54-0.5)(0.54-0.6)\\
	&\approx0.620219+(-1.46300)\times(0.54-0.5)(0.54-0.6)\\
	&\approx-0.616707\\
	\end{aligned}
	$\\
	则$\ln 0.54\approx P_2(0.54)\approx-0.616839$
	\subsection*{problem 4}
	\markright{problem 4}
	\addcontentsline{toc}{subsection}{problem 4}
	\paragraph{解}由于步长$h=1^{'}=(1/60)^{\circ}$，区间为$0^{\circ}-90^{\circ}$，则区间划分为：
	$$x_i=\frac{\pi\cdot i}{5400},\ i=0,1,2,3,\cdots,5400$$
	用函数值和近似值所建立的线性插值多项式分别为：\\
	$$
	\begin{aligned}
	&L_1(x)=\frac{x-x_{i+1}}{x_i-x_{i+1}}f(x_i)+\frac{x-x_i}{x_{i+1}-x_i}f(x_{i+1})\\
	&L_1^{*}(x)\frac{x-x_{i+1}}{x_i-x_{i+1}}f^{*}(x_i)+\frac{x-x_i}{x_{i+1}-x_i}f^{*}(x_{i+1})\\
	\end{aligned}
	$$\\
	其中$x\in[x_i,x_{i+1}]$从而:
	$$
	\begin{aligned}
	|\cos x-L_1^{*}(x)|&=|\cos x-L_1(x)+L_1(x)-L_1^{*}(x)|\\
	&\leq|\cos x-L_1(x)|+|L_1(x)-L_1^{*}(x)|\\
	\end{aligned}
	$$\\
	由插值余项公式，截断误差:
	$$
	\begin{aligned}
	|\cos x-L_1(x)|&=|\frac{1}{2!}(-\cos \xi)(x-x_i)(x-x_{i+1})|\\
	&\leq\frac{1}{2}|(x-x_i)(x-x_{i+1})|\\
	&\leq \frac{1}{2}\max_{x_{i}\leq x\leq x_{i+1}}|(x-x_i)(x-x_{i+1})|\\
	&\leq \frac{1}{2}(\frac{1}{2}\cdot\frac{\pi}{60\times180})^2
	\approx1.06\times10^{-8}\\
	\end{aligned}
	$$\\
	舍入误差:
	$$
	\begin{aligned}
	|L_1(x)-L_1^{*}(x)|&=|(f(x_i)-f^{*}(x_i))+(f(x_{i+1})-f^{*}(x_{i+1}))|\\
	&\leq|e(f^{*}(x_i))|\cdot|\frac{x_{i+1}-x}{x_i-x_{i+1}}|+|e(f^{*}(x_{i+1}))|\cdot|\frac{x-x_i}{x_{i+1}-x_i}|\\
	&\leq max{|e(f^{*}(x_i))|,|e(f^{*}(x_{i+1}))|}(\frac{x_{i+1}-x}{x_{i+1}-x_i}+\frac{x-x_i}{x_{i+1}-x_i})\\
	&=max{|e(f^{*}(x_i))|,|e(f^{*}(x_{i+1}))|}
	\leq\frac{1}{2}\times10^{-5}\\
	\end{aligned}
	$$\\
	因此误差界为：$|\cos x-L_1^{*}(x)|\leq1.06\times10^{-8}+\frac{1}{2}\times10^{-5}=0.50106\times10^{-5}.$\\
	\subsection*{problem 6}
	\markright{problem 6}
	\addcontentsline{toc}{subsection}{problem 6}
	\subsubsection*{(1)}
	\paragraph{证明}对$k=0,1,2,\cdots,n$，令$f(x)=x^k$，则函数的n次插值多项式为:
	$$L_n(x)=\sum_{j=0}^{n}x_j^kl_j(x),$$
	插值余项为:
	$$R_n(x)=f(x)-L_n(x)=\frac{1}{(n+1)!}f^{n+1}(\xi)\omega_{n+1}(x).$$
	由$k\leq n$，则$f^{n+1}(\xi)=0$，则$R_n(x)=0$，即$f(x)=L_n(x)$，则\\
	$$\sum_{j=0}^{n}x_j^kl_j(x)\equiv x^k(k=0,1,2,\cdots,n).$$
	\subsubsection*{(2)}
	\paragraph{证明}对$k=0,1,2,\cdots,n$，由二项式定理:
	$$(x_j-x)^k=\sum_{i=0}^{k}\binom{k}{i}x_j^{i}(-x)^{k-i},$$
	由(1)可得:
	$$
	\begin{aligned}
	\sum_{j=0}^{k}(x_j-x)^kl_j(x)&=\sum_{j=0}^{k}\bigg(
	\sum_{i=0}^{k}\binom{k}{i}x_j^{i}(-x)^{k-i}\bigg)
	l_j(x)\\
	&=\sum_{i=0}^{k}\binom{k}{i}(-x)^{k-i}(\sum_{j=0}^{k}x_j^{i}l_j(x))\\
	&=\sum_{i=0}^{k}\binom{k}{i}(-x)^{k-i}x^i\\
	&=(x-x)^i\\
	\end{aligned}
	$$\\
	即$$\sum_{j=0}^{k}(x_j-x)^kl_j(x)\equiv0(k=0,1,2,\cdots,n).\\$$
	\subsection*{problem 8}
	\markright{problem 8}
	\addcontentsline{toc}{subsection}{problem 8}
	\paragraph{解}设在区间$[-4,4]$上以h为步长的等距节点的二次插值函数为$L_h(x)$，余项为$R_h(x)$.\\
	对任意$x\in[-4,4]$，设$x\in[x_{i-1},x_{i+1}]$，则插值余项为:
	$$R_h(x)=\frac{1}{3!}f^{'''}(\xi)(x-x_{i-1})(x-x_i)(x-x_{i+1}).$$
	令$x=x_i+th$，则$x_{i-1},x_i,x_{i+1}$分别对应$t=1,0,-1$，且
	$$(x-x_{i-1})(x-x_i)(x-x_{i+1})=(t-1)t(t+1)h^3.$$
	记$\varphi(t)=(t-1)t(t+1)$，则$\varphi^{'}(t)=3t^2-1$，易知$t\in[1,-1],|\varphi(t)|=\frac{2\sqrt{3}}{9}$，即:
	$$
	\begin{aligned}
	|R_h(x)|&=\frac{|f^{'''}(\xi)|}{6}|(x-x_{i-1})(x-x_i)(x-x_{i+1})|\\
	&\leq\frac{e^4}{6}\cdot\frac{2\sqrt{3}}{9}h^3\\
	&=\frac{\sqrt{3}h^3}{27}\cdot54.6\\
	&\leq10^{-6}\\
	\end{aligned}
	$$
	解得$h\leq0.0066.$
	\subsection*{problem 19}
	\markright{problem 19}
	\addcontentsline{toc}{subsection}{problem 19}
	\paragraph{解}因为$P(0)=P^{'}(0)=0$，则$x=0$为二重根，设方程为:
	$$P(x)=x^2(ax^2+bx+c).$$
	由$P(1)=P^{'}(1)=1,P(2)=1$，则有:
	$$
	\left\{
	\begin{aligned}
	&a+b+c=1\\
	&4a+3b+2c=1\\
	&4(4a+2b+c)=1\\
	\end{aligned}
	\right.
	$$
	解得$a=\frac{1}{4},b=-\frac{3}{2},c=\frac{9}{4}$，则:
	$$P(x)=x^2(\frac{1}{4}x^2-\frac{3}{2}x+\frac{9}{4}).$$
\end{document}